package leetcode.秋招.字节跳动.字节研发在线编程;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/7/25 16:21
 * @description：https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf?tpId=190&&tqId=35976&rp=1&ru=/activity/oj&qru=/ta/job-code-high-rd/question-ranking
 */
public class NC119最小的K个数 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.GetLeastNumbers_Solution_heap(new int[]{0,1,1,1,4,5,3,7,7,8,10,2,7,8,0,5,2,16,12,1,19,15,5,18,2,2,22,15,8,22,17,6,22,6,22,26,32,8,10,11,2,26,9,12,9,7,28,33,20,7,2,17,44,3,52,27,2,23,19,56,56,58,36,31,1,19,19,6,65,49,27,63,29,1,69,47,56,61,40,43,10,71,60,66,42,44,10,12,83,69,73,2,65,93,92,47,35,39,13,75}, 75));
    }

    public class Solution {
        public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
            ArrayList<Integer> res = new ArrayList<>();
            if (k > input.length || k == 0) return res;
            PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
            for (int i = 0; i < k; i++) {
                queue.offer(input[i]);
            }
            for (int i = k; i < input.length; i++) {
                if (queue.peek() > input[i]) {
                    queue.poll();
                    queue.offer(input[i]);
                }
            }
            for (int i = 0; i < k; i++) {
                res.add(queue.poll());
            }
            return res;
        }

        //有问题
        public ArrayList<Integer> GetLeastNumbers_Solution_heap(int [] input, int k) {
            ArrayList<Integer> res = new ArrayList<>();
            if (k > input.length || k == 0) return res;
            for (int i = input.length / 2 - 1; i >= 0; i--) {
                adjust(input, i, input.length);
            }
            System.out.println(Arrays.toString(input));
            for (int i = input.length - 1; i >= input.length - k ; i--) {
                int tmp = input[i];
                input[i] = input[0];
                input[0] = tmp;
                res.add(input[0]);
            }
            return res;
        }

        public void adjust(int[]arr, int parentIndex, int len) {
            int temp = arr[parentIndex];
            int childIndex = parentIndex * 2 + 1;
            while (childIndex < len) {
                if (childIndex + 1 < len && arr[childIndex + 1] < arr[childIndex]) {
                    childIndex++;
                }
                if (temp <= arr[childIndex]) break;
                arr[parentIndex] = arr[childIndex];
                parentIndex = childIndex;
                childIndex = 2 * childIndex + 1;
            }
            arr[parentIndex] = temp;
        }
    }
}
